Regiony

Limit pamięci: 128 MB

Agencja Rozwoju Regionalnego Narodów Zjednoczonych (UNRDA) ma dobrze zdefiniowaną strukturę organizacyjną. Zatrudnia łącznie osób, z których każda pochodzi z jednego z regionów geograficznych świata. Pracownicy są ponumerowani od do w porządku ważności, przy czym pracownik numer , Dyrektor, jest najważniejszą osobą w agencji. Regiony są ponumerowane od do w jakimkolwiek porządku. Każdy pracownik z wyjątkiem Dyrektora posiada jednego bezpośredniego przełożonego. Przełożony jest zawsze ważniejszy niż każdy z jego pracowników.

Powiemy, że pracownik jest menadżerem pracownika , wtedy i tylko wtedy, gdy jest przełożonym lub jest menadżerem przełożonego . W ten sposób, na przykład, Dyrektor jest menadżerem każdego z pozostałych pracowników. Ponadto, oczywiście, żadna para pracowników nie może być wzajemnie swoimi menadżerami.

Niestety, Biuro Śledcze Narodów Zjednoczonych (UNBI) otrzymało ostatnio szereg skarg na to, że struktura organizacyjna UNRDA nie jest zrównoważona i wyróżnia pewne regiony świata w stosunku do innych. Aby zweryfikować te oskarżenia, UNBI potrzebuje systemu komputerowego, który dysponując strukturą organizacyjną UNRDA, mógłby odpowiadać na zapytania postaci: dla dwóch różnych regionów i , ile jest par pracowników agencji i , takich że pracownik pochodzi z regionu , pracownik pochodzi z regionu oraz jest menadżerem . Każde zapytanie ma dwa parametry - regiony i - natomiast jego wynikiem jest jedna liczba całkowita - liczba różnych par i , które spełniają wyżej wymienione warunki.

Zadanie

Napisz program, który mając dane regiony pochodzenia wszystkich pracowników agencji, a także dane o tym, kto jest czyim przełożonym, odpowie na opisane wyżej zapytania.

Ograniczenia

- liczba pracowników
- liczba regionów
- liczba zapytań, na które ma odpowiedzieć twój program
- region pochodzenia pracownika (przy czym )
- przełożony pracownika (przy czym )
- regiony pojawiające się w danym zapytaniu

Wejście

Twój program powinien wczytać ze standardowego wejścia następujące dane:

• Pierwszy wiersz zawiera liczby całkowite , i , w tej kolejności, pooddzielane pojedynczymi odstępami.
• Kolejne wierszy opisuje pracowników agencji w porządku ważności. -ty z tych wierszy opisuje pracownika numer . Pierwszy z tych wierszy (tzn. ten opisujący Dyrektora) zawiera jedną liczbę całkowitą: region pochodzenia Dyrektora. Każdy z pozostałych wierszy zawiera dwie liczby całkowite oddzielone pojedynczym odstępem: identyfikator przełożonego -tego pracownika oraz region pochodzenia -tego pracownika.
• Następnie następuje opis zapytań. Każde zapytanie jest zawarte w jednym wierszu standardowego wejścia i składa się z dwóch różnych liczb całkowitych oddzielonych pojedynczym odstępem - regionów oraz .

Wyjście

Na standardowe wyjście wypisać należy wierszy, zawierających odpowiedzi na kolejne zapytania. Odpowiedź na każde zapytanie musi być zawarta w jednym wierszu standardowego wyjścia, zawierającym jedną liczbę całkowitą - liczbę par pracowników UNRDA i , takich że regionem pochodzenia jest , regionem pochodzenia jest oraz jest menadżerem .

Uwaga: Dane testowe będą tak dobrane, że poprawna odpowiedź na każde z zapytań podanych na standardowym wejściu będzie zawsze mniejsza niż .

Ocenianie

W testach wartych łącznie 30 punktów nie przekroczy 500.
W testach wartych łącznie 55 punktów z żadnego regionu nie będzie pochodziło więcej niż 500 pracowników.
Testy, w których zachodzą oba powyższe warunki, są warte 15 punktów.
Testy, w których zachodzi co najmniej jeden z tych dwóch warunków, są warte 70 punktów.

Przykład

Dla danych wejściowych:

6 3 4
1
1 2
1 3
2 3
2 3
5 1
1 2
1 3
2 3
3 1

poprawną odpowiedzią jest:

1
3
2
1